A switching network typically is made of input ports and output ports that are interconnected by switches and wires. The switching network serves primarily to correctly route messages from the input ports to the output ports. Each wire in the network serves as a conduit for transmitting a message from one of its ends to the other of its ends. The term wire, in this context, or the terms connection or connector, includes any means for communicating data between switches, such as electrical wires, parallel groups of wires, optical fibers, multiplexed channels over single wires, or free space radio or optical communication paths.
The switch is an atomic unit that resembles a switching network in function (i.e., a switch has inputs and outputs and connects the inputs to the outputs in any desired pattern). The degree of a switch is the number of inputs and outputs in the switch. For example, as shown in FIG. 1 a 2.times.2 switch 2 has a degree of four.
A switching network may route any kind of digital or analog data including voice or video signals. It can also route address information that specifies the correct output for the message, and routing information that helps direct the message to the correct output or that establishes communications links such as in a telephone network. In some networks, the routing is accomplished by setting switches so that input ports become directly connected to output ports (e.g., in a telephone network). In other networks, the inputs ports do not become directly connected to the output ports. Instead, the messages are routed as packets through the network in steps.
Switching networks are widely used to route messages and to establish communications among multiple parties. Typical examples of networks in which switching networks are used include telephone networks, data networks, computer networks, and interconnection networks in parallel data processing systems.
There are several varieties of switching networks that are classified by the manner in which messages are handled by the network. Common types of switching networks include packet-switching, circuit-switching, cut-through, and worm-hole networks.
In a packet-switching network, packets are treated as atomic objects. At each time step, each wire in the packet-switching network can transmit an entire packet from one switch to another switch. If necessary, packets may be queued in buffers located at the switches or at the wires of the network. These networks are also often referred to as store-and-forward networks. The name "store and forward" is derived from the characteristic of the networks that packets are temporarily stored in the queues and then forwarded to the next destination in the network.
A circuit switching network is appropriate when messages are too large to be treated as atomic objects (such as packets). In this type of network, a dedicated path is established in the switching network between the sender and receiver of each message. The paths corresponding to different messages are disjoint (i.e., they do not share any wires). Once a path is established, the sender can transmit an arbitrarily long message to the receiver without interference from the other messages. This model is also called the lock-down model, and most closely resembles the approach adopted by current telephone networks.
The wormhole and cut-through networks are best classified as lying in a class situated between the packet and circuit-switching networks. In a wormhole network, a packet is assumed to consist of a sequence of flits (a flit is typically a bit or a byte). At the end of each wire is a buffer that can hold a small number of flits (typically two flits). A packet is not stored entirely in one buffer, but instead is spread out over a quantity of wires indicated by the packet length (number of flits) and by the buffer size. A packet can be thought of as a worm proceeding head-first through the network. Behind the head, each flit of the worm advances only if there is adequate space in the buffer at the end of the next wire to hold the flit. When the head moves, the buffer space it frees up trickles back to the tail, allowing the entire worm to move. If blocked, a packet compresses (like an accordion) to a length acceptable for the buffer size at the appropriate node. The integrity of the packet is also preserved (i.e., it cannot be cut in half by another packet). In a cut-through network, the buffer size is large enough that the entire packet can accumulate at a single node.